Data centers incorporate switched fabrics containing switches that perform route lookup operations needed to determine where to send a packet having a given destination address. A destination address carried within each packet uniquely identifies the endpoint to which the packet should be sent. An example of such switches are Ethernet switches.
Each Ethernet switch has a number of bidirectional Ethernet ports. When a switch receives a packet it uses the destination address to determine the desired output port and then sends that packet through the output port to the next Ethernet switch or endpoint device in the fabric. The choice of output port at each hop determines a route through the Ethernet fabric. In order to maintain correct communications, the route for each address must finally reach the destination Ethernet endpoint that is indicated by the target address from any point in the fabric.
Existing Ethernet switches process arbitrarily chosen Ethernet addresses. When a packet arrvies at a switch, the switch must use the packet's destination Ethernet address to quickly determine a route or destination port to which that packet should be sent. Forwarding tables are used to define a route for each Ethernet endpoint within a cluster. When Ethernet addresses are arbitrarily selected, and fast lookup is required, expensive associative lookup hardware is commonly used to quickly determine the route for the packet. Some high performance solutions rely primarily on Content Addressable Memories (CAMs) to quickly identify a packet route for arbitrarily assigned Ethernet addresses. Fast content addressable memories are expensive to build in hardware.
Software-based lookup and look-up techniques implemented in inexpensive hardware are much cheaper but introduce significant routing latency.
What is desired is a solution which provides low latency or fast route lookup while leveraging lower cost conventional memory types. In the case of Ethernet switches, it is desirable that the solution also conforms to Ethernet standards.